A sorting algorithm is an algorithm that places elements of a list in a specified order. For example, a sorting algorithm may be applied to a list of numbers to place the numbers in numerical order or to a list of words to place the words in lexicographical order. Numerous sorting algorithms exist, such as, but not limited to Bubble Sort, Selection Sort, Merge Sort, and Quicksort. Each of these sorting algorithms has advantages and disadvantages relative to other sorting algorithms. For example, sorting algorithms may be classified according to their computational complexity, memory usage, stability, and adaptability, among other factors.
One of the more popular sorting algorithms in practice is Quicksort. Quicksort is classified as a divide-and-conquer algorithm. In other words, the Quicksort algorithm works by recursively breaking down a problem into two or more sub-problems, continuing further to break down the problems until they are much simpler to solve individually. The solutions to the sub-problems are then combined to achieve the solution for the original problem. The Quicksort algorithm, in particular, divides a set of data into subsets of data by performing a partition operation around a pivot. In this operation, all elements smaller (or lesser in value) than the pivot are placed in a first subset and all elements larger (or greater in value) than the pivot are placed in a second subset. Elements equal in value to the pivot may be placed in either the first or the second subset, according to the particular implementation of the algorithm. The first and second subsets are then similarly sorted in a recursive manner.
One application in which the Quicksort algorithm is often used is the market clearing aspect of a bidding system (e.g., an auction). Market clearing refers to the element of a bidding process by which bids are analyzed to determine a winning bid. Depending on the number of bids to be analyzed, the bidding process may require a large amount of resources to sort through and determine a winning bid. Thus, scalability is an important feature of an auction marketplace.
Although a conventional Quicksort algorithm may suit the needs of an auction marketplace that hosts a relatively large number of actors, such an algorithm may become prohibitively inefficient to use when the number of actors grows above a certain threshold. For example, auctions conducted over the Internet may involve numerous actors throughout the world. As the number of actors and bids increase, the computational overhead associated with the sorting of bids may become a bottleneck in the auction process.